import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/9 17:36
 * @description 将问题抽象为 完全背包问题，每种硬币无限，组成面额x的最少硬币。
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] cs = {1, 2, 5};
        solution2.coinChange(cs, 11);
    }
    int INF = 0x3f3f3f3f;
    public int coinChange(int[] cs, int cnt) {
        int n = cs.length;
        // f[i]代表组成面额 i的最少硬币
        int[] f = new int[cnt + 1];
        for (int i = 1; i <= cnt; i++) f[i] = INF;
        for (int i = 1; i <= n; i++) {
            int val = cs[i - 1];
            // 完全背包问题，面额等价与重量，f[j]取决于上一行f[j]和 这一行 f[j-val]的值，我们希望f[j-val]是更新过得，需要从小到大遍历
            for (int j = val; j <= cnt; j++) {
                f[j] = Math.min(f[j], f[j - val] + 1);
            }
        }
        return f[cnt] == INF ? -1 : f[cnt];
    }
}
